﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;

//杨辉三角
//https://leetcode.cn/problems/pascals-triangle/description/


//class Solution {
//public:
//   vector<vector<int>> generate(int numRows) {
//       vector<vector<int>> s(numRows);
//	   for (size_t i = 0; i < numRows; i++)
//	   {
//		   s[i].resize(i + 1);
//		   s[i][0] = 1;
//		   s[i][i] = 1;
//
//	   }
//	   for (size_t i = 2; i < numRows; i++)
//	   {
//		   for (size_t j = 1; j < i; j++)
//		   {
//			   s[i][j] = s[i - 1][j - 1] + s[i - 1][j];
//		   }
//	   }
//	   return s;
//    }
//};

//删除排序数组中的重复项
//https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//       
//        int x = 0, y = 0;
//
//        while (y < nums.size()) //使用双指针法，x表示未重复的的位置，y用比较后面的数是否重复。
//        {
//            if (nums[x] != nums[y]) //不重复就让x下一个位置放上与前面值不重复的值，然后x在等于这新的不重复值的位置
//            {
//                x++;
//                nums[x] = nums[y];
//            }
//            y++;//无论重不重复y都要向后走进行比较
//           
//        }
//        return ++x;
//    }
//};

//数组中出现次数超过一半的数字
//https ://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param numbers int整型vector
//     * @return int整型
//     */
//    int MoreThanHalfNum_Solution(vector<int>& numbers) {
//        
//        sort(numbers.begin(), numbers.end()); //利用排序
//        int mid = numbers.size() == 1 ? 0 : numbers.size() / 2;//由于这个数超过一半，经过排序数组中间肯定有这个数
//        return  numbers[mid];//时间复杂度O(NlogN)非最优解
//        // write code here
//    }
//};



//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param numbers int整型vector
//     * @return int整型
//     */
//    int MoreThanHalfNum_Solution(vector<int>& numbers) {
//        int count = 1;//数字出现次数
//        int num = numbers[0];
//        for (size_t i = 1; i < numbers.size(); i++) //如果这个数与后面的数不同count--；如果相同就++；
//        {                                           //如果count为0这个数就等于后面的那个数，最后保存下来的那个数是出现最多的
//            if (count == 0)
//            {
//                num = numbers[i];
//            }
//            if (num != numbers[i])
//            {
//                count--;
//            }
//            if (num == numbers[i])
//            {
//                count++;
//            }
//        }
//        return num;
//        // write code here
//    }
//};
//


